//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 577 👎 0


package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class 最小的k个数 {
    public static void main(String[] args) {
        Solution solution = new 最小的k个数().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        public int[] getLeastNumbers(int[] arr, int k) {
            int[] vec = new int[k];
            if (k == 0 ) return vec;
            PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });

            for (int i = 0; i < k; i++) {
                queue.offer(arr[i]);
            }

            for (int i = k; i < arr.length; i++) {
                if (queue.peek() > arr[i]){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }

            for (int i = 0; i < k; i++) {
                vec[i] = queue.poll();
            }
            return vec;
        }
        
        
        
        
        
        
        
        int[] arr;
        int k;
        boolean jdg = false;
        public int[] getLeastNumbers1(int[] arr, int k) {
            this.arr = arr;
            this.k = k;
            quick_sort(0, arr.length - 1);
            return Arrays.copyOfRange(arr, 0, k);
        }

        void quick_sort(int left, int right) {
            if (left >= right || jdg) return;
            int l = left, r = right;
            while (l < r) {
                while (l < r && arr[l] <= arr[r]) l++;
                swap(l, r);
                while (l < r && arr[l] <= arr[r]) r--;
                swap(l, r);
            }
            if (l == k) {
                jdg = true;
                return;
            }
            if (l < k) {
                quick_sort(l + 1, right);
            }
            quick_sort(left, l - 1);
        }

        void swap(int a, int b) {
            int tmp = arr[a];
            arr[a] = arr[b];
            arr[b] = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
